package com.leetcode.algorithm.y19.m04;

/**
 * leetcode-cn.com
 * 
 * (done)189. 旋转数组
 * (done)151. 翻转字符串里的单词
 * (done)557. 反转字符串中的单词 III
 * (done)26. 删除排序数组中的重复项
 * (done)283. 移动零
 * @author: jie.deng
 * @time: 2019年4月15日 上午11:34:01
 */
public class MySolution0415 {
    
    /**
     * 189. 旋转数组 
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     * 
     * 示例 1:
     * 输入: [1,2,3,4,5,6,7] 和 k = 3 
     * 输出: [5,6,7,1,2,3,4] 
     * 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 
     * 向右旋转 2 步: [6,7,1,2,3,4,5] 
     * 向右旋转 3 步: [5,6,7,1,2,3,4] 
     * 
     * 示例 2:
     * 输入: [-1,-100,3,99] 和 k = 2 
     * 输出: [3,99,-1,-100] 
     * 解释: 向右旋转 1 步: [99,-1,-100,3] 
     * 向右旋转 2 步: [3,99,-1,-100] 
     * 
     * 说明:
     * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 
     * 要求使用空间复杂度为 O(1) 的原地算法。
     * 
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) {
            return;
        }
        k = k % len;
        // 每次移动k个位置，
        // 先移动索引为nums.length-1,nums.length-1-k,...
        // 第二轮nums.length-2,nums.length-2-k...
        // ...
        // 最后一轮nums.length-k,然后nums.length-k-k,...
        int[] tail = new int[k];
        for (int i = 1; i <= k; i++) {
            int j = len - i;
            int tmp = nums[j];
            while (j >= k) {
                nums[j] = nums[j - k];
                j -= k;
            }
            tail[k - i] = tmp;
        }
        for (int i = 0; i < k; i++) {
            nums[i] = tail[i];
        }
    }
    
    /**
     * 151. 翻转字符串里的单词
     * 
     * 给定一个字符串，逐个翻转字符串中的每个单词。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入: "the sky is blue"
     * 输出: "blue is sky the"
     * 示例 2：
     * 
     * 输入: "  hello world!  "
     * 输出: "world! hello"
     * 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
     * 示例 3：
     * 
     * 输入: "a good   example"
     * 输出: "example good a"
     * 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
     *  
     * 
     * 说明：
     * 
     * 无空格字符构成一个单词。
     * 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
     * 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
     *  
     * 
     * 进阶：
     * 
     * 请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        if (s == null) {
            return null;
        }
        String[] arr = s.split(" ");
        StringBuilder strBuilder = new StringBuilder();

        for (int i = arr.length - 1; i >= 0; i--) {
            if (!"".equals(arr[i])) {
                strBuilder.append(" ");
                strBuilder.append(arr[i]);
            }
        }
        if (strBuilder.length() > 1) {
            strBuilder.deleteCharAt(0);
        }
        return strBuilder.toString();
    }
    
    
    /**
     * 557. 反转字符串中的单词 III
     * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     * 
     * 示例 1:
     * 
     * 输入: "Let's take LeetCode contest"
     * 输出: "s'teL ekat edoCteeL tsetnoc" 
     * 注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
     * @param s
     * @return
     */
    public String reverseWordsIII(String s) {
        StringBuffer ret = new StringBuffer();
        String[] words = s.split(" ");
        for (int i = 0; i < words.length; i++) {
            if (i != 0) {
                ret.append(" ");
            }
            ret.append(new StringBuffer(words[i]).reverse());
        }
        return ret.toString();
    }
    
    /**
     * 26. 删除排序数组中的重复项 
     * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
     * 
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 
     * 示例 1:
     * 给定数组 nums = [1,1,2],
     * 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
     * 你不需要考虑数组中超出新长度后面的元素。 
     * 示例 2:
     * 给定 nums = [0,0,1,1,1,2,2,3,3,4],
     * 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
     * 你不需要考虑数组中超出新长度后面的元素。 
     * 
     * 说明:
     * 为什么返回数值是整数，但输出的答案是数组呢?
     * 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     * 你可以想象内部操作如下:
     * // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums);
     * // 在函数里修改输入数组对于调用者是可见的。 
     * // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 
     * for (int i = 0; i < len; i++) { print(nums[i]); }
     * 
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int len = nums.length;
        if (len == 0) {
            return len;
        }
        int newLen = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] != nums[newLen-1]) {
                nums[newLen] = nums[i];
                newLen++;
            }
        }
        return newLen;
    }   
    
    /**
     * 283. 移动零 
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 
     * 示例:
     * 输入: [0,1,0,3,12] 
     * 输出: [1,3,12,0,0] 
     * 
     * 说明:
     * 必须在原数组上操作，不能拷贝额外的数组。 
     * 尽量减少操作次数。
     * 
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        int k = -1;// 记录最后一个非0元素的索引
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                nums[++k] = nums[i];
            }
        }
        for (int i = k + 1; i < len; i++) {
            nums[i] = 0;
        }
    }    
}
